package org.ranki.moerae.lachesis;

import org.ranki.moerae.clotho.node.AbstractNode;
import org.ranki.moerae.clotho.context.Context;

import java.util.*;

public class Djstra implements Search{
    private volatile static Djstra djstra;
    private Djstra (){}
    public static Djstra getDjstra() {
        if (djstra == null) {
            synchronized (Djstra.class) {
                if (djstra == null) {
                    djstra = new Djstra();
                }
            }
        }
        return djstra;
    }
    @Override
    public void search(AbstractNode start, AbstractNode end, Context ctx) {
        Map<AbstractNode,List<AbstractNode>> path=new HashMap<>();
        Map<AbstractNode,Integer> close=new HashMap<>();
        Queue<AbstractNode> open=new PriorityQueue<>((a,b)-> (int) (close.getOrDefault(a,Integer.MAX_VALUE>>1)-
                            close.getOrDefault(b,Integer.MAX_VALUE>>1)));
        open.offer(start);
        path.put(start,new ArrayList<AbstractNode>(){{add(start);}});
        while (!open.isEmpty()){
            AbstractNode curr= open.poll();
            int currTime= close.getOrDefault(curr,0);
            List<AbstractNode> prePath=path.get(curr);
            for(AbstractNode next:curr.getNexts()){
                if(!next.canDeal(ctx)){
                    continue;
                }
                Integer time=close.getOrDefault(next,Integer.MAX_VALUE>>1);
                if(time> next.getAveCostTime()){
                    if(time!=Integer.MAX_VALUE>>1){
                        open.remove(next);//松弛
                    }
                    close.put(next,currTime+next.getAveCostTime());
                    List<AbstractNode> newPath=new ArrayList<>(prePath);
                    newPath.add(next);
                    path.put(next,newPath);
                    if(next==end){
                        ctx.getParams().put("path",path.get(next));
                        return;
                    }
                    open.offer(next);
                }
            }
        }
    }
}
